package com.its.myalgorithm.day04;

import java.util.ArrayList;
import java.util.List;

/**
 * @projectName: dgl-algorithm
 * @package: com.its.myalgorithm.day04
 * @className: ReverseDoubleNode
 * @author: DONG GL
 * @description: TODO 反转双链表
 * @date: 2022/4/2 9:46
 * @version: 1.0
 */
public class ReverseDoubleNode {

    /**
     * 双链表反转
     *
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleNode(DoubleNode head) {
        //当前head节点的上一个节点
        DoubleNode pre = null;
        //当前head节点的下一个节点
        DoubleNode next = null;
        while (head!= null) {
            //记录head的下一个值
            next = head.next;
            //head反转
            head.next = pre;
            head.last = next;
            //pre 记录当前位置
            pre = head;
            //head 向下移动
            head = head.next;
        }
        return pre;
    }


    /**
     * 双链表反转
     *
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleNode2(DoubleNode head) {
        if (head == null) {
            return null;
        }
        //所有的head集合
        List<DoubleNode> list = new ArrayList<DoubleNode>();
        while (head != null) {
            list.add(head);
            head= head.next;
        }
        list.get(0).next = null;

        //当前head节点的上一个节点
        DoubleNode pre = null;
        //当前head节点的下一个节点
        DoubleNode next = null;
        while (head!= null) {
            //记录head的下一个值
            next = head.next;
            //head反转
            head.next = pre;
            head.last = next;
            //pre 记录当前位置
            pre = head;
            //head 向下移动
            head = head.next;
        }
        return pre;
    }


    public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
        DoubleNode end = null;
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            end = head;
            head = head.next;
        }
        for (int i = 0; i < origin.size(); i++) {
            if (!origin.get(i).equals(end.value)) {
                return false;
            }
            end = end.last;
        }
        return true;
    }

    public static void main(String[] args) {
        int len = 100;
        int maxValuse = 100;
        int testTime = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            DoubleNode head = ListArrayUtils.generateRandomDoubleList(len, maxValuse);
            DoubleNode doubleNode = reverseDoubleNode(head);
            List<Integer> doubleListOriginOrder = ListArrayUtils.getDoubleListOriginOrder(head);
            if (!checkDoubleListReverse(doubleListOriginOrder, doubleNode)) {
                System.out.println("链表反转出错了");
            }
        }
        System.out.println("测试结束");

    }
}
